用栈来求解汉诺塔问题

[编程题]用栈来求解汉诺塔问题

热度指数：2314 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有n层的时候，打印最优移动过程和最优移动总步数。

输入描述:

输入一个数n，表示塔层数

输出描述:

按样例格式输出最优移动过程和最优移动总步数

示例1

输入

输出

Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.

说明

当塔数为两层时，最上层的塔记为1，最下层的塔记为2

备注:

算法知识视频讲解

Python 3

徐熊涛

#用python3写

import sys

class HanoiProblem():
def __init__(self):
self.lS=[]
self.mS=[]
self.rS=[]
self.lS.append(100)
self.mS.append(100)
self.rS.append(100)
self.No='No'
self.LToM='LToM'
self.MToL='MToL'
self.MToR='MToR'
self.RToM='RToM'
def fStackTotstack(self,record, preNoAct, nowAct, fStack,tStack,From,To):
if ((record[0]!=preNoAct) and (fStack[-1] < tStack[-1])):
tStack.append(fStack.pop())
print("Move "+ str(tStack[-1])+ " from "+From+" to "+To)
record[0]=nowAct
return 1
return 0

def start(self,num,left,mid,right):
for i in range(num,0,-1):
self.lS.append(i)
record=[self.No]
step=0
while (len(self.rS)!=num+1):
step += self.fStackTotstack(record, self.MToL,self.LToM, self.lS, self.mS, left, mid)
step += self.fStackTotstack(record, self.LToM,self.MToL, self.mS, self.lS, mid, left)
step += self.fStackTotstack(record, self.RToM,self.MToR, self.mS, self.rS, mid, right)
step += self.fStackTotstack(record, self.MToR,self.RToM, self.rS, self.mS, right, mid)
return step

num=int(input())
HP=HanoiProblem()
result=HP.start(num,'left','mid','right')
print('It will move {} steps.'.format(result))

发表于 2021-08-16 14:09:50 回复(0)